home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / awe2-0_1.lha / awe2-0.1 / Src / RCS / ThreadEventPairingHeap.cc,v < prev    next >
Text File  |  1988-10-12  |  10KB  |  386 lines
  1. head     1.1;
  2. access   ;
  3. symbols  ;
  4. locks    grunwald:1.1; strict;
  5. comment  @@;
  6.  
  7.  
  8. 1.1
  9. date     88.10.12.10.50.43;  author grunwald;  state Exp;
  10. branches ;
  11. next     ;
  12.  
  13.  
  14. desc
  15. @@
  16.  
  17.  
  18.  
  19. 1.1
  20. log
  21. @Initial revision
  22. @
  23. text
  24. @// This may look like C code, but it is really -*- C++ -*-
  25. /* 
  26. Copyright (C) 1988 Free Software Foundation
  27.     written by Dirk Grunwald (grunwald@@cs.uiuc.edu)
  28.     adapted for libg++ by Doug Lea (dl@@rocky.oswego.edu)
  29.  
  30. This file is part of GNU CC.
  31.  
  32. GNU CC is distributed in the hope that it will be useful,
  33. but WITHOUT ANY WARRANTY.  No author or distributor
  34. accepts responsibility to anyone for the consequences of using it
  35. or for whether it serves any particular purpose or works at all,
  36. unless he says so in writing.  Refer to the GNU CC General Public
  37. License for full details.
  38.  
  39. Everyone is granted permission to copy, modify and redistribute
  40. GNU CC, but only under the conditions described in the
  41. GNU CC General Public License.   A copy of this license is
  42. supposed to have been given to you along with GNU CC so you
  43. can know your rights and responsibilities.  It should be in a
  44. file named COPYING.  Among other things, the copyright notice
  45. and this notice must be preserved on all copies.  
  46. */
  47.  
  48.  
  49. #include "stream.h"
  50. #include "ThreadEventPairingHeap.h"
  51. //
  52. //    This defines a Pairing Heap structure for a pointer data type.
  53. //
  54. //    See ``The Pairing Heap: A New Form of Self-Adjusting Heap''
  55. //    Fredman, Segdewick et al,
  56. //    Algorithmica (1986) 1:111-129
  57. //
  58. //    In particular, this implements the pairing heap using the circular
  59. //    list.
  60. //
  61. //
  62.  
  63. #define MIN_STORAGE_SIZE  8
  64.  
  65. // error handling
  66.  
  67.  
  68. void default_ThreadEventPairingHeap_error_handler(char* msg)
  69. {
  70.   cerr << "Fatal ThreadEventPairingHeap error. " << msg << "\n";
  71.   exit(1);
  72. }
  73.  
  74. one_arg_error_handler_t ThreadEventPairingHeap_error_handler = default_ThreadEventPairingHeap_error_handler;
  75.  
  76. one_arg_error_handler_t set_ThreadEventPairingHeap_error_handler(one_arg_error_handler_t f)
  77. {
  78.   one_arg_error_handler_t old = ThreadEventPairingHeap_error_handler;
  79.   ThreadEventPairingHeap_error_handler = f;
  80.   return old;
  81. }
  82.  
  83. void ThreadEventPairingHeap::error(const char* msg)
  84. {
  85.   (*ThreadEventPairingHeap_error_handler)(msg);
  86. }
  87.  
  88. ThreadEventPairingHeap::ThreadEventPairingHeap(int length = 0)
  89. {
  90.   freelist = ThreadEventPairingHeapIndex_NULL;
  91.   root = ThreadEventPairingHeapIndex_NULL;
  92.   allocatedSize = 0;
  93.   elements = 0;
  94.   make_room(length);
  95. }
  96.  
  97. ThreadEventPairingHeapIndex ThreadEventPairingHeap::get_cell()
  98. {
  99.   if (freelist == ThreadEventPairingHeapIndex_NULL)
  100.     make_room(0);
  101.  
  102.   ThreadEventPairingHeapIndex cell = freelist;
  103.   storage[freelist].valid = 1;
  104.   freelist = storage[freelist].sibling;
  105.   elements++;
  106.   return(cell);
  107. }
  108.  
  109. void ThreadEventPairingHeap::return_cell(ThreadEventPairingHeapIndex cell)
  110. { 
  111.   storage[cell].sibling = freelist;
  112.   storage[cell].valid = 0;
  113.   freelist = cell;
  114.   elements--;
  115. }
  116.  
  117. void ThreadEventPairingHeap::make_room(int atLeast)
  118. {
  119.   if (freelist == ThreadEventPairingHeapIndex_NULL) 
  120.   {
  121.     if (allocatedSize > 0) 
  122.     {
  123.       ThreadEventPairingHeapIndex newSize = (allocatedSize * 3) / 2;
  124.  
  125.       ThreadEventPairingHeapRecord *newStorage = new ThreadEventPairingHeapRecord[newSize];
  126.       if (newStorage == 0)
  127.         error("make_room: out of space");
  128.       for (int i = 0; i < allocatedSize; ++i)
  129.       {
  130.         newStorage[i].item = storage[i].item;
  131.         newStorage[i].valid = storage[i].valid;
  132.         newStorage[i].sibling = storage[i].sibling;
  133.         newStorage[i].children = storage[i].children;
  134.       }
  135.       delete [allocatedSize] storage;
  136.       storage = newStorage;
  137.       for (i = allocatedSize; i < newSize; i++) 
  138.       {
  139.         storage[i].sibling = i+1;
  140.         storage[i].valid = 0;
  141.       }
  142.       storage[newSize-1].sibling = ThreadEventPairingHeapIndex_NULL;
  143.       freelist = allocatedSize;
  144.       allocatedSize = newSize;
  145.     } 
  146.     else 
  147.     {
  148.       if (atLeast <= MIN_STORAGE_SIZE) 
  149.         allocatedSize = MIN_STORAGE_SIZE;
  150.       else
  151.         allocatedSize = atLeast;
  152.       storage = new ThreadEventPairingHeapRecord[allocatedSize];
  153.       if (storage == 0)
  154.         error("make_room: out of space");
  155.       for (int i = 0; i < allocatedSize; i++) 
  156.       {
  157.         storage[i].sibling = i+1;
  158.         storage[i].valid = 0;
  159.       }
  160.       storage[allocatedSize-1].sibling = ThreadEventPairingHeapIndex_NULL;
  161.       freelist = 0;
  162.     }
  163.   }
  164. }
  165.  
  166. //
  167. //  make_child is not used since its
  168. //  code has now been directly encorporated into enq/del_front
  169. //
  170. // make_child takes two nodes and makes one the child of the other
  171. // and returns the index of the new parent. 
  172. //
  173. // We play fast and loose with the siblings field of a & b, although
  174. // we maintain the siblings of the children.
  175. //
  176. ThreadEventPairingHeapIndex ThreadEventPairingHeap::make_child(ThreadEventPairingHeapIndex a, 
  177.                                                ThreadEventPairingHeapIndex b)
  178. {
  179.   ThreadEventPairingHeapIndex parent;
  180.   ThreadEventPairingHeapIndex child;
  181.     
  182.   if (storage[a].item < storage[b].item)
  183.   {
  184.     parent = a; child = b;
  185.   } 
  186.   else 
  187.   {
  188.     parent = b; child = a;
  189.   }
  190.   //
  191.   // If the new parent has no children, simply add the new child.
  192.   // We assume that the child and the parent dont care about
  193.   // their *sibling* nodes
  194.   //
  195.   ThreadEventPairingHeapIndex popsKid = storage[parent].children;
  196.     
  197.   if (popsKid == ThreadEventPairingHeapIndex_NULL) 
  198.   {
  199.     storage[parent].children = child;
  200.     storage[child].sibling = child;
  201.   } 
  202.   else 
  203.   {
  204.     ThreadEventPairingHeapIndex temp = storage[popsKid].sibling;
  205.     storage[popsKid].sibling = child;
  206.     storage[child].sibling = temp;
  207.     storage[parent].children = child;
  208.   }
  209.   return(parent);
  210. }
  211.  
  212.  
  213. ThreadEventPairingHeapIndex ThreadEventPairingHeap::enq(ThreadEvent  item)
  214. {
  215.   ThreadEventPairingHeapIndex cell = get_cell();
  216.   
  217.   storage[cell].item = item;
  218.   storage[cell].children = ThreadEventPairingHeapIndex_NULL;
  219.   storage[cell].sibling = ThreadEventPairingHeapIndex_NULL;
  220.   
  221.   if (root == ThreadEventPairingHeapIndex_NULL) 
  222.     return root = cell;
  223.   else 
  224.   {
  225.     ThreadEventPairingHeapIndex parent;
  226.     ThreadEventPairingHeapIndex child;
  227.     
  228.     if ( storage[root].item <  storage[cell].item )
  229.     {
  230.       parent = root; child = cell;
  231.     } 
  232.     else 
  233.     {
  234.       parent = cell; child = root;
  235.     }
  236.     ThreadEventPairingHeapIndex popsKid = storage[parent].children;
  237.     
  238.     if (popsKid == ThreadEventPairingHeapIndex_NULL) 
  239.     {
  240.       storage[parent].children = child;
  241.       storage[child].sibling = child;
  242.     } 
  243.     else 
  244.     {
  245.       ThreadEventPairingHeapIndex temp = storage[popsKid].sibling;
  246.       storage[popsKid].sibling = child;
  247.       storage[child].sibling = temp;
  248.       storage[parent].children = child;
  249.     }
  250.     root = parent;
  251.     return cell;
  252.   }
  253. }
  254.  
  255. //
  256. //    Item removal is the most complicated routine.
  257. //
  258. //    We remove the root (should there be one) and then select a new
  259. //    root. The siblings of the root are in a circular list. We continue
  260. //    to pair elements in this list until there is a single element.
  261. //    This element will be the new root.
  262.  
  263. int ThreadEventPairingHeap::del_front()
  264. {
  265.   int valid = FALSE;
  266.   do 
  267.   {
  268.     if (root == ThreadEventPairingHeapIndex_NULL || elements <= 0) 
  269.       return(0);
  270.  
  271.     valid = storage[root].valid;
  272.     ThreadEventPairingHeapIndex child = storage[root].children;
  273.     return_cell(root);
  274.     
  275.     if (child == ThreadEventPairingHeapIndex_NULL)
  276.         root = ThreadEventPairingHeapIndex_NULL;
  277.     else 
  278.     {
  279.       while(storage[child].sibling != child) 
  280.       {
  281.         // We have at least two kids, but we may only have
  282.         // two kids. So, oneChild != child, but it is possible
  283.         // that twoChild == child.
  284.         
  285.         ThreadEventPairingHeapIndex oneChild = storage[child].sibling;
  286.         ThreadEventPairingHeapIndex twoChild = storage[oneChild].sibling;
  287.  
  288.         // Remove the two from the sibling list
  289.  
  290.         storage[child].sibling = storage[twoChild].sibling;
  291.         storage[oneChild].sibling = ThreadEventPairingHeapIndex_NULL;
  292.         storage[twoChild].sibling = ThreadEventPairingHeapIndex_NULL;
  293.         
  294.         ThreadEventPairingHeapIndex bestChild;
  295.         ThreadEventPairingHeapIndex worstChild;
  296.     
  297.         if (storage[oneChild].item < storage[twoChild].item) 
  298.         {
  299.           bestChild = oneChild; worstChild = twoChild;
  300.         } 
  301.         else 
  302.         {
  303.           bestChild = twoChild; worstChild = oneChild;
  304.         }
  305.         ThreadEventPairingHeapIndex popsKid = storage[bestChild].children;
  306.         
  307.         if (popsKid == ThreadEventPairingHeapIndex_NULL) 
  308.         {
  309.           storage[bestChild].children = worstChild;
  310.           storage[worstChild].sibling = worstChild;
  311.         } 
  312.         else 
  313.         {
  314.           ThreadEventPairingHeapIndex temp = storage[popsKid].sibling;
  315.           storage[popsKid].sibling = worstChild;
  316.           storage[worstChild].sibling = temp;
  317.           storage[bestChild].children = worstChild;
  318.         }
  319.         if (twoChild == child) 
  320.         {
  321.           // We have reduced the two to one, so we'll be exiting.
  322.           child = bestChild;
  323.           storage[child].sibling = child;
  324.         } 
  325.         else 
  326.         {
  327.           // We've removed two siblings, now we need to insert
  328.           // the better of the two
  329.           storage[bestChild].sibling = storage[child].sibling;
  330.           storage[child].sibling = bestChild;
  331.           child = storage[bestChild].sibling;
  332.         }
  333.       }
  334.       root = child;
  335.     }
  336.   } while ( !valid );
  337.  
  338.   return 1;
  339. }
  340.  
  341. int ThreadEventPairingHeap::del(ThreadEventPairingHeapIndex i) 
  342. {
  343.   if (storage[i].valid)
  344.   {
  345.     if (i == root)
  346.       del_front();
  347.     else
  348.     {
  349.       storage[i].valid = 0;
  350.       elements--;
  351.     }
  352.     return 1;
  353.   }
  354.   else
  355.     return 0;
  356. }
  357.  
  358. ThreadEventPairingHeapTrav::ThreadEventPairingHeapTrav(ThreadEventPairingHeap& a)
  359. {
  360.   h = &a;
  361.   for (current = 0; current < h->allocatedSize; current++) 
  362.     if (h->storage[current].valid)
  363.         return;
  364.   current = ThreadEventPairingHeapIndex_NULL;
  365. }
  366.  
  367. void ThreadEventPairingHeapTrav::del()
  368. {
  369.   if (current == ThreadEventPairingHeapIndex_NULL)
  370.     h->error("del of null traverser");
  371.   h->del(current);
  372. }
  373.  
  374. void ThreadEventPairingHeapTrav::advance()
  375. {
  376.   if (current == ThreadEventPairingHeapIndex_NULL)
  377.     return;
  378.   
  379.   for (current++; current < h->allocatedSize; current++) 
  380.     if (h->storage[current].valid)
  381.         return;
  382.   current = ThreadEventPairingHeapIndex_NULL;
  383. }
  384.  
  385. @
  386.